package com.fyt.algorithm.Leecode.day1;


import org.junit.Test;


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/*
链表反转!!!!
*/

public class TwoNumberAdd {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public int statisticsSum(ListNode ln) {
        int res = 1;
        while (ln.next != null) res++;
        return res;
    }


    /**
     * 链表反转,并且返回新的头节点
     *
     * @param ln
     * @return
     */
    public static ListNode reverseListNode(ListNode ln) {

        if (ln == null || ln.next == null) {
            return ln;
        }
        ListNode newHead = reverseListNode(ln.next);
        ListNode pre = ln.next;
        pre.next = ln;
        ln.next = null;

        return newHead;
    }


/*    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode newl1 = l1;
        ListNode newl2 = l2;
        ListNode res = null;
        int Tag = 0;
        while (newl1 != null && newl2 != null) {

            int x = (newl1.val + newl2.val + Tag) % 10;
            res = new ListNode(x, res);   //指向上一个节点,即上一个基位,,这是当前最新节点
            newl1=newl1.next;
            newl2=newl2.next;

            if (newl1.val + newl2.val >= 10) {
                Tag = 1;
            } else Tag = 0;

        }

        ListNode head= reverseListNode(res);

        if(newl1!=null){
            newl1.val=newl1.val+Tag;
            res.next=newl1;
        }
        if(newl2!=null){
            newl2.val=newl2.val+Tag;
            res.next=newl2;
        }



       *//* int num1 = statisticsSum(l1);
        int num2 = statisticsSum(l2);
        int mylength = num1 >= num2 ? num1 : num2;*//*


        return head;
    }*/


    /*public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // 创建一个虚拟头节点
        ListNode current = dummy;
        int carry = 0; // 进位标志

        while (l1 != null || l2 != null || carry != 0) { // 确保进位也被处理
            int x = (l1 != null) ? l1.val : 0; // 如果 l1 不为空，取其值；否则取 0
            int y = (l2 != null) ? l2.val : 0; // 如果 l2 不为空，取其值；否则取 0

            int sum = x + y + carry; // 当前位的总和
            carry = sum / 10; // 更新进位
            current.next = new ListNode(sum % 10); // 创建新节点并连接到结果链表

            current = current.next; // 移动到下一个节点
            if (l1 != null) l1 = l1.next; // 如果 l1 不为空，移动到下一个节点
            if (l2 != null) l2 = l2.next; // 如果 l2 不为空，移动到下一个节点
        }

        return dummy.next; // 返回结果链表（跳过虚拟头节点）
    }*/

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;

        while (l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;


            cur.next = new ListNode((x + y + carry) % 10);

            cur=cur.next;
          if(l1!=null)l1=l1.next;
          if(l2!=null) l2=l2.next;


            carry = (x + y + carry) / 10;


        }
        //如果要增加位,或者说相加后比最大链表要长;
        if(carry==1) cur.next=new ListNode(1);

        return pre.next;
    }


    public static void show(ListNode listNode) {
        System.out.println(listNode.val);
        if (listNode.next != null) {

            show(listNode.next);
        }

    }


    public void test() {
        ListNode listNode1 = new ListNode(1, null);
        ListNode listNode2 = new ListNode(2, listNode1);
        ListNode listNode3 = new ListNode(3, listNode2);
        ListNode listNode4 = new ListNode(4, listNode3);
        ListNode listNode5 = new ListNode(5, listNode4);



        ListNode listNode6 = new ListNode(1, null);
        ListNode listNode7 = new ListNode(2, listNode6);
        ListNode listNode8 = new ListNode(3, listNode7);
        ListNode listNode9 = new ListNode(4, listNode8);
        ListNode listNode10 = new ListNode(5, listNode9);

        show(listNode5);
    }


    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1, null);
        ListNode listNode2 = new ListNode(2, listNode1);
        ListNode listNode3 = new ListNode(3, listNode2);
        ListNode listNode4 = new ListNode(4, listNode3);
        ListNode listNode5 = new ListNode(5, listNode4);


        ListNode listNode6 = new ListNode(5, null);
        ListNode listNode7 = new ListNode(4, listNode6);
        ListNode listNode8 = new ListNode(3, listNode7);
        ListNode listNode9 = new ListNode(2, listNode8);
        ListNode listNode10 = new ListNode(1, listNode9);


        show(addTwoNumbers(listNode10, listNode10));

        // show(reverseListNode(listNode5));
    }
}
